package com.desin.modle.datastruct.algo.backtrackingAlgorithm.pattern;

public class Solution {
    private boolean match = false;

    private char[] pattern;

    private int plen;

    public Solution(String patternStr){
        char[] chars = patternStr.toCharArray();
        this.pattern = chars;
        this.plen = chars.length;
    }

    public boolean match(String text){
        match = false;
        char[] charArray = text.toCharArray();
        rmacth(0,0,charArray,charArray.length);
        return match;
    }

    private void rmacth(int ti, int pi, char[] chars, int tlen) {
        if(match == true){
            return;
        }
        if(pi==plen){
            if(ti==tlen){
                match = true;
            }
            return;
        }
        if(pattern[pi]=='*'){
            for(int i=0;i<=tlen-ti;i++){
                rmacth(ti+i,pi+1,chars,tlen);
            }
        }else if(pattern[pi]=='?'){
            rmacth(ti,pi+1,chars,tlen);
            rmacth(ti+1,pi+1,chars,tlen);
        }else if(ti<tlen&&pattern[pi]==chars[ti]){
            rmacth(ti+1,pi+1,chars,tlen);
        }
    }
}
